package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2020/12/2
 * @description: 将二叉搜索树变平衡 https://leetcode-cn.com/problems/balance-a-binary-search-tree/
 */
public class B_1382_将二叉搜索树变平衡 {

	/**
	 * first version
	 * 本来想着通过
	 * 从下往上的递归方式 + 后序遍历 ，先找出最低的不平衡的节点，然后通过 AVL的旋转的方式让其达到平衡，再一步步调节到根节点
	 * -- 但是由于 TreeNode 不能存储 height ，容易导致重复计算！于是放弃这个思路！
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode balanceBST(TreeNode root) {
		balanceBST(root.left, root);
		balanceBST(root.right, root);
		balanceBST(root, null);
		return root;
	}

	static void balanceBST(TreeNode grand, TreeNode prev) {
		if (!isBalanced(grand)) {
			reBalance(grand, prev);
		}
	}

	/**
	 * 判断节点是否是平衡的
	 *
	 * @param root
	 * @return
	 */
	static boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
	}

	/**
	 * @param node
	 * @return
	 */
	static int height(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return Math.max(height(node.left), height(node.right)) + 1;
	}

	/**
	 * 调整平衡
	 * 通过 AVL 的方式调整平衡
	 * 但是 高度这块不好处理，还是不方便用 AVL tree!
	 * 冲突点： AVLNode 没有存储 height
	 *
	 * @param grand
	 * @param prev
	 */
	static void reBalance(TreeNode grand, TreeNode prev) {

	}


	/**
	 * 通过中序遍历，将节点的值存放到 数组里。
	 * 此时数组是排好序的数组，那么只需要将数组转换为 二叉搜索树 就能完成目的！
	 * -- 思维是很巧妙的！
	 * 二叉搜索树 <-> 动态数组集合(需要索引进行快速定位！) 之间的转换
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode balanceBSTByArrayList(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		inorder(root, list);
		// 偏向右边的一个
		int mid = list.size() >> 1;
		TreeNode nRoot = new TreeNode(list.get(mid));
		nRoot.left = buildTree(list, 0, mid - 1);
		nRoot.right = buildTree(list, mid + 1, list.size() - 1);
		return nRoot;
	}

	/**
	 * 中序遍历将 二叉搜索树的元素添加到 list 中
	 * 老子就是想用迭代实现中序遍历！
	 * 迭代还是要好好想想的！..
	 * 如果不能直接默出来的话，那我得好好反思：到底是思路没有打通，还是思路通了以后写不出来
	 *
	 * @param node
	 * @param list
	 */
	public static void inorder(TreeNode node, List<Integer> list) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = node;

		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			//此时 cur = null
			cur = stack.pop();
			//处理节点
			list.add(cur.val);
			cur = cur.right;
		}

	}

	public static TreeNode buildTree(List<Integer> list, int start, int end) {
		if (start > end) {
			return null;
		}
		int mid = (start + end) >> 1;
		TreeNode node = new TreeNode(list.get(mid));
		node.left = buildTree(list, start, mid - 1);
		node.right = buildTree(list, mid + 1, end);
		return node;
	}


	public static void main(String[] args) {
		TreeNode root = TreeNode.stringToTreeNode("[1,null,2,null,3,null,4,null,null]");
		balanceBSTByArrayList(root);
	}
}
